package main

var answers = make(map[int]int)

func numTrees(n int) int {
	if n == 0 || n == 1 {
		return 1
	}
	if v, ok := answers[n]; ok {
		return v
	}
	ans := 0
	for r := 1; r <= n; r++ {
		ans += numTrees(r-1) * numTrees(n-r)
	}
	answers[n] = ans
	return ans
}

func main() {
	for i := 0; i < 19; i++ {
		println(i, numTrees(i))
	}
}
